package com.wuyou.mid;

import java.util.Arrays;

/**
 * @Description 611. 有效三角形的个数（两边之差小于第三边,两边之和大于第三边）
 * @Author 无忧
 * @Date 2023/4/4 10:11
 */
public class TriangleNumber {

    public static void main(String[] args) {
        int[] nums = {2, 2, 3, 4};

        System.out.println(sol_2(nums));
    }


    public static int sol_2(int[] nums) {
        int ans = 0;
        Arrays.sort(nums);
        for (int i = 0; i <= nums.length - 2; i++) {
            int a = nums[i];
            for (int j = i + 1; j <= nums.length - 1; j++) {
                int b = nums[j], l = j + 1, r = nums.length - 1;
                int sub = b - a, sum = b + a;
                while (l < nums.length && nums[l] >= sum) {
                    l++;
                }
                while (r > j && nums[r] >= sum) {
                    r --;
                }
                ans += Math.max((r - l) + 1, 0);
            }
        }
        return ans;
    }


    /**
     * 执行用时：2227 ms, 在所有 Java 提交中击败了 5.02% 的用户
     *
     * @param nums
     * @return int
     * @author 无忧
     * @date 2023/4/4 11:26
     */
    public static int sol_1(int[] nums) {
        int ans = 0;
        Arrays.sort(nums);
        for (int i = 0; i <= nums.length - 2; i++) {
            int a = nums[i];
            for (int j = i + 1; j <= nums.length - 1; j++) {
                int b = nums[j];
                int l = j + 1, r = nums.length, mid = 0;
                while (l < nums.length) {
                    if (b - a < nums[l] && b + a > nums[l]) {
                        l++;
                        ans++;
                    } else {
                        if (b - a >= nums[l] || b + a <= nums[l]) {
                            l++;
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        return ans;
    }
}
